/**
 * Created with IntelliJ IDEA.
 * Description:二叉搜索树
 * User: 徐海涛
 * Date: 2022-02-21
 * Time: 13:50
 */
//二叉搜索树
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node(int val) {
        this.val = val;
    }
}

public class BinarySearchTree {
    public Node root = null;//根节点
    //查找key在不在二叉搜索树中
    public Node search(int key) {
         Node cur = root;
         //这里分三种情况
         while (cur != null) {
             //1.如果cur的值刚好等于key
             if(cur.val == key) {
                 return cur;
                 //2.如果cur.val 小于 key
                 //那么要查找的key 在 其右子树
             }else if(cur.val < key) {
                 cur = cur .right;
                 //3.如果cur.val 大于 key
                 //那么要查找的 key 在 其左子树
             }else {
                 cur = cur.right;
             }
         }
         return null;//代表没有这个数据
    }

//二叉搜索树插入一个key
    //对于二叉搜索树来说 插入的数据一定是 叶子节点
    public boolean insert(int val) {
        //如果是空数 直接插入
        if(root == null) {
            root = new Node(val);//root等于新插入的节点，节点的值为val
            return true;
        }
        //如果不是 空数 那么 接下来我们去找叶子节点
        Node cur = root;//一样的 用cur代替root
        Node parent = null;//用一个双亲节点
        while (cur != null) {
            //1,如果val的值大于cur 那么val 在cur的右子树
            if(cur.val < val) {
                parent = cur;
                cur = cur.right;
                //2.如果val的值刚好等于cur的值 不能插入
            }else if(cur.val == val) {
                return false;//不能有相同的数据进行插入
                //3.如果val的值小于cur 那么val 在cur的左子树
            }else {
                parent = cur;
                cur = cur.left;
            }
        }
        //找到叶子节点以后我们要去比较parent.val 和val的大小再进行插入
        Node node = new Node(val);//新节点val
        if(parent.val < val) {
            parent.right = node;//这里根据二叉搜索树的性质，parent为根节点
            //val比根节点大所以在根节点右边
        }else {
            parent.left = node;
        }
        return true;
    }

    //二叉搜素数 删除操作（难点）
    public void  remove(int key) {
        Node cur = root;
        Node parent = null;
        while (cur != null) {
            if(cur.val == key) {
                removeNode(cur,parent);
                break;
            }else if(cur.val<key) {
                parent = cur;
                cur = cur.right;
            }else {
                parent = cur;
                cur = cur.left;
            }
        }
    }

    public void removeNode(Node cur,Node parent) {
        //第一种情况 cur.left == null
        if (cur.left == null) {
            //1.cur是root 则 root = cur.right
            if (cur == root) {
                root = cur.right;
                //2.cur不是root cur是parent.left
            } else if (cur == parent.left) {
                parent.left = cur.right;
                //3，cur不是root cur是parent.right
            } else {
                parent.right = cur.right;
            }
            //第二种情况 cur.right == null
        } else if (cur.right == null) {
            //1，cur是root root = cur.left
            if (cur == root) {
                root = cur.left;
                //2.cur不是root cur是parent.left
            } else if (cur == parent.left) {
                parent.left = cur.left;
                //3，cur不是root cur是parent.right
            } else {
                parent.right = cur.left;
            }
            //第三种情况 cur.left!=null && cur.right!=null（难点）
            //1.cur的左树当中找最大值2.cur的右树当中找最小值
            //核心就是替换
        } else {
            Node targetParent = cur;
            Node targer = cur.right;
            //左树找不等于空的时候
            while (targer.left != null) {
                targetParent = targer;
                targer = targer.left;
            }
            //交换值
            cur.val = targer.val;
            //这里判断ta是tp的左还是右
            if (targer == targetParent.left) {
                targetParent.left = targer.right;
            } else {
                targetParent.right = targer.right;
            }
        }
    }
}
